package com.hdu.hot100.backTrack;

public class lc79 {
    class Solution {
        boolean[][] used;
        int[][] directions = new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

        public boolean exist(char[][] board, String word) {
            used = new boolean[board.length][board[0].length];
            for (int i = 0; i < board.length; i++) {
                for (int j = 0; j < board[0].length; j++) {
                    if (word.charAt(0) == board[i][j] && f(board, 0, word, i, j)) {
                        return true;
                    }
                }
            }
            return false;
        }

        boolean f(char[][] board, int index, String word, int row, int col) {
            if (row < 0 || row >= board.length || col < 0 || col >= board[0].length) {
                return false;
            }
            if (used[row][col]) {
                return false;
            }
            if (board[row][col] != word.charAt(index)) {
                return false;
            }
            if (index == word.length() - 1) {
                return true;
            }
            used[row][col] = true;
            boolean flag = false;
            for (int[] direction : directions) {
                int newRow = row + direction[0];
                int newCol = col + direction[1];
                flag = f(board, index + 1, word, newRow, newCol);
                if (flag) {
                    break;
                }
            }
            used[row][col] = false;
            return flag;
        }
    }
}
